package one.three.thirtyEight;

public class GeneralizedQueueBeta<Item> {

	private Node<Item> first;
	private Node<Item> last;
	private int n;

	public void enqueue(Item item) {
		if (first == null) {
			first = new Node<Item>();
			first.value = item;
			last = first;
		} else {
			last.next = new Node<Item>();
			last.next.value = item;
			last.next.pre = last;
			last = last.next;
		}
		n++;
	}

	public Item dequeue() {
		if (!isEmpty()) {
			Item r = first.value;
			first = first.next;
			if (first != null) {
				first.pre = null;
			}
			n--;
			return r;
		} else {
			return null;
		}
	}

	public Item delete(int k) {
		if (k <= n) {
			Node<Item> c = first;
			for (int i = 0; i < k - 1; i++) {
				c = c.next;
			}
			Item r = c.value;
			n--;
			if (c.pre != null) {
				c.pre.next = c.next;
			}
			if (c.next != null) {
				c.next.pre = c.pre;
			}
			return r;
		}
		return null;
	}

	public boolean isEmpty() {
		return first == null;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Item v;
		sb.append("<");
		Node<Item> c = first;
		while (c != null) {
			sb.append("[" + c.value + "]");
			c = c.next;
		}
		sb.append(")");
		return sb.toString();
	}

	private class Node<Item> {
		Node<Item> pre;
		Node<Item> next;
		Item value;
	}

	public static void main(String[] args) {
		GeneralizedQueueBeta<String> q = new GeneralizedQueueBeta<String>();
		q.enqueue("a");
		q.enqueue("b");
		q.enqueue("c");

		System.out.println(q);

		String r = q.delete(1);
		System.out.println(r);
		System.out.println(q);
	}

}
